/**
 * @file array.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-01
 *
 * @copyright Copyright (c) 2021
 *
 * 31.栈的压入、弹出序列
 * 39.数组中出现次数超过一半的数字
 * 29.顺时针打印矩阵
 * 42.连续子数组的最大和
 *
 * 数位操作，我直接复制粘贴
 * 43.1~n整数中1出现的次数
 * 44.数字序列中某一位的数字
 *
 * 61.扑克牌中的顺子
 */

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 31.判断栈的弹出序列是否合法
    bool validateStackSequences(vector<int> &pushed, vector<int> &popped)
    {
        int n = pushed.size();
        stack<int> stk;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            stk.push(pushed[i]);
            // cout << "push " << pushed[i] << endl;
            while (!stk.empty() && popped[j] == stk.top()) {
                // cout << "pop " << stk.top() << endl;
                stk.pop();
                ++j;
            }
        }
        return j == n;
    }

    // 39. 求众数
    int majorityElement(vector<int> &nums)
    {
        // 法一：遍历，计数打表，当某个数的计数>n/2就是众数
        // 法二：排序，中间的数就是众数
        // 法三：摩尔投票法
        // 假设众数是x，遇到x，cnt加一；非x，cnt减一，当cnt==0时切换众数
        // 因为众数比其他所有数加起来还要多
        int cnt = 0;
        int res = nums[0];
        for (int i = 0; i < nums.size(); ++i) {
            if (0 == cnt) {
                res = nums[i];
            }
            if (nums[i] == res) {
                ++cnt;
            } else {
                --cnt;
            }
        }
        return res;
    }
    // 29. 顺时针打印矩阵
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        // 简单模拟
        int m = matrix.size();
        if (m == 0) {
            return {};
        }
        int n = matrix[0].size();
        vector<int> res(m * n, 0);
        int idx = 0;
        int l = 0, r = n - 1, t = 0, b = m - 1;
        while (1) {
            for (int i = l; i <= r; ++i) {
                res[idx++] = matrix[t][i];
            }
            if (++t > b) { // t完成自增
                break;
            }
            for (int i = t; i <= b; ++i) {
                res[idx++] = matrix[i][r];
            }
            if (l > --r) {
                break;
            }
            for (int i = r; i >= l; --i) {
                res[idx++] = matrix[b][i];
            }
            if (t > --b) {
                break;
            }
            for (int i = b; i >= t; --i) {
                res[idx++] = matrix[i][l];
            }
            if (++l > r) {
                break;
            }
        }
        return res;
    }
    // 42.
    int maxSubArray(vector<int> &nums)
    {
        // 贪心：碰到和为负直接重新计数
        // 因为负数对 ‘和’ 负贡献
        int sum = 0;
        int res = nums[0];
        for (int &num : nums) {
            if (sum < 0) {
                sum = 0;
            }
            sum += num;
            res = max(res, sum);
        }
        return res;
    }
    // 43.
    int countDigitOne(int n)
    {
        long long digit = 1;
        int res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                res += high * digit;
            } else if (cur == 1) {
                res += high * digit + low + 1;
            } else {
                res += (high + 1) * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
    // 44.
    int findNthDigit(int n)
    {
        int digit = 1;
        long long start = 1;
        long long count = 9;
        while (n > count) { // 1.
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long long num = start + (n - 1) / digit;           // 2.
        return std::to_string(num)[(n - 1) % digit] - '0'; // 3.
    }
    // 61.
    bool isStraight(vector<int> &nums)
    {
        // 顺子必满足max-min<5 且无重复牌 除大小王
        std::sort(nums.begin(), nums.end());
        int j = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i] == 0) {
                ++j;
            } else if (nums[i] == nums[i + 1]) {
                return false;
            }
        }
        return nums[4] - nums[j] < 5;
    }
};

void test31()
{
    vector<int> pushed = {1, 2, 3, 4, 5};
    vector<int> popped1 = {4, 5, 3, 2, 1};
    vector<int> popped2 = {4, 3, 5, 1, 2};
    vector<int> popped3 = {1, 2, 3, 4, 5};
    cout << Solution().validateStackSequences(pushed, popped1) << endl;
    cout << Solution().validateStackSequences(pushed, popped2) << endl;
    cout << Solution().validateStackSequences(pushed, popped3) << endl;
}

void test39()
{
    vector<int> nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
    cout << Solution().majorityElement(nums) << endl;
}

void test29()
{
    vector<vector<int>> matrix0 = {};
    vector<vector<int>> matrix1 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    vector<vector<int>> matrix2 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
    vector<vector<int>> matrix3 = {{1, 2}, {4, 5}, {7, 8}}; // 竖矩形
    vector<vector<int>> matrix4 = {{1}, {4}, {7}};
    vector<vector<int>> matrix5 = {{1, 2, 3}, {4, 5, 6}}; // 横矩形
    vector<vector<int>> matrix6 = {{1, 2, 3}};
    print(Solution().spiralOrder(matrix0));
    print(Solution().spiralOrder(matrix1));
    print(Solution().spiralOrder(matrix2));
    print(Solution().spiralOrder(matrix3));
    print(Solution().spiralOrder(matrix4));
    print(Solution().spiralOrder(matrix5));
    print(Solution().spiralOrder(matrix6));
}

int main(int argc, const char **argv)
{
    // test31();
    // test39();
    // test29();
    return 0;
}